package leetcode.problems;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by gmwang on 2018/7/25
 * 组合求和
 */
public class _0903CombinationSumIII {
    /**
     * Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
     * 找出所有可能的k个数字的组合，这些组合加到一个数字n上，假设只能使用从1到9的数字，并且每个组合应该是一组唯一的数字。
     * Note:
     * <p>
     * All numbers will be positive integers.
     * The solution set must not contain duplicate combinations.
     * Example 1:
     * <p>
     * Input: k = 3, n = 7
     * Output: [[1,2,4]]
     * Example 2:
     * <p>
     * Input: k = 3, n = 9
     * Output: [[1,2,6], [1,3,5], [2,3,4]]
     * /**
     *
     * @param k,n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List list = new ArrayList<>();
        List subList = new ArrayList<>();
        List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
        subList(list,subList,intList,n,k,0);
        return list;
    }
    public void subList(List list,List subList,List<Integer> intList,int target,int size,int start){
        if(target ==0 && subList.size() == size){
            list.add(new ArrayList<>(subList));
            return;
        }
        if(target < 0) return;
        for (int i = start; i < intList.size(); i++) {
            subList.add(intList.get(i));
            subList(list,subList,intList,target - intList.get(i),size,i+1);
            subList.remove(subList.size() - 1);
        }
    }
    @Test
    public void test() {
//        int k = 3;
//        int n = 7;
        int k = 3;
        int n = 9;
        List res = combinationSum3(k, n);
        System.out.println(res);
    }

}
